package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Objects;

import cn.edu.jxau.util.Deque;

public class Main {

    public static void main(String[] args) {

        final int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
        final int W = 3; // 窗口大小
        System.out.println(Arrays.toString(getMaxWindow(arr, 3)));
    }

    private static int[] getMaxWindow(int[] arr, int windowSize) {

        // 参数校验 //
        Objects.requireNonNull(arr, "参数arr不能为null");
        if (arr.length == 0) {
            throw new IllegalArgumentException("参数arr不能是空数组");
        }
        if (windowSize <= 0) {
            throw new IllegalArgumentException("参数windowSize不能是负数");
        }

        // get max window //
        Deque<Integer> deque = new Deque<Integer>();
        int[] res = new int[arr.length - windowSize + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!deque.isEmpty() && arr[deque.peekLast()] <= arr[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (deque.peekFirst() == i - windowSize) {
                deque.pollFirst();
            }
            if (i >= windowSize - 1) {
                res[index++] = arr[deque.peekFirst()];
            }
        }
        return res;
    }
}

/**
 * 暴力破解，差评
 * @author 付大石
 */
//public class Main {
//
//    public static void main(String[] args) {
//
//        final int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
//        final int N = arr.length; // 数组长度
//        final int W = 3; // 窗口大小
//        List<Integer> list = new ArrayList<>(); //记录各个窗口的最大值
//        for(int i=0;i<N-W+1;i++) {
//            list.add(getMax(Arrays.copyOfRange(arr, i, i+W)));
//        }
//        System.out.println(list);
//    }
//    
//    private static int getMax(int... arr) {
//
//        Objects.requireNonNull(arr, "参数arr不能是null");
//        if (arr.length == 0) {
//            throw new IllegalArgumentException("参数arr不能是空数组");
//        }
//        int max = arr[0];
//        for (int i = 1; i < arr.length; i++) {
//            if(max < arr[i]) { //找到更大的值
//                max = arr[i];
//            }
//        }
//        return max;
//    }
//}
